/**
 * 
 */
package string.passed;

import java.util.Stack;

/**
 * @author xyyi
 *
 */
public class ValidParentheses {

	/**
		Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
		
		The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
	*/
	public boolean isValid(String s) {

		Stack<Character> stack = new Stack<Character>();

		for (char c : s.toCharArray()) {
			if (isLeft(c))
				stack.push(c);
			else {
				if (stack.isEmpty())
					return false;
				if (!isPair(stack.pop(), c)) {
					return false;
				}
			}
		}

		return stack.isEmpty();
	}

	private int currIndex = 1;

	public boolean isValidRecursive(String s, int level) {
		return false;
	}

	private boolean isLeft(char c) {
		return c == '(' || c == '[' || c == '{';
	}

	private boolean isPair(char c1, char c2) {
		return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']')
				|| (c1 == '{' && c2 == '}');
	}

	/**
	 * 
	 */
	public ValidParentheses() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
